package com.dyz.leetcode._20_dynamicProgramming._494;

public class findTargetSumWays01 {
    // DFS 解法
    private int ans = 0;
    public int findTargetSumWays(int[] nums, int S) {
        dfs(nums, S, 0, 0);
        return ans;
    }

    private void dfs(int[] nums, int S, int i, int sum) {
        if (i == nums.length) {
            if (sum == S) {ans++;}
            return;
        }

        dfs(nums, S, i + 1, sum + nums[i]);
        dfs(nums, S, i + 1, sum - nums[i]);
    }
}
